package com.algorithm.ch2.cjm.dynamic;

/**
 * Created by jieming.chen on 2020/7/6
 */
public class CoinChange {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;

        int[] fn = new int[amount + 1];
        fn[0] = -1;
        fn[1] = 1;
        fn[2] = 1;
        fn[3] = 2;
        fn[4] = 2;
        fn[5] = 1;
        fn[6] = 2;
        fn[7] = 2;
        fn[8] = 3;
        fn[9] = 3;
        fn[10] = 2;
        fn[11] = 3;

        CoinChange coinChange = new CoinChange();
        System.out.println(coinChange.coinChange(coins, amount));


        int[] coins1 = {2};
        int amount1 = 10;

        int[] fn1 = new int[amount1 + 1];
        fn[0] = -1;
        fn[1] = -1;
        fn[2] = 1;
        fn[3] = -1;
        fn[4] = 2;
        fn[5] = -1;
        fn[6] = 3;
        fn[7] = -1;
        fn[8] = 4;
        fn[9] = -1;
        fn[10] = 5;

        System.out.println(coinChange.coinChange(coins1, amount1));


        int[] coins2 = {2, 5};
        int amount2 = 10;

        int[] fn2 = new int[amount2 + 1];
        fn[0] = -1;
        fn[1] = -1;
        fn[2] = 1;
        fn[3] = -1;
        fn[4] = 2;
        fn[5] = 1;
        fn[6] = 3;
        fn[7] = 2;
        fn[8] = 4;
        fn[9] = 3;
        fn[10] = 2;

        System.out.println(coinChange.coinChange(coins2, amount2));

//        CoinChange coinChange = new CoinChange();
//        int[] aa = {2};
//        System.out.println(coinChange.coinChange(aa, 1));

        int[] aa = {2};
        System.out.println(coinChange.coinChange(aa, 0));
    }

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        // 存放走的最少步骤
        int[] fn = new int[amount + 1];
        for (int i = 0; i < amount + 1; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] == i) {
                    min = 1;
                } else if (i > coins[j] && fn[i - coins[j]] != -1) {
                    min = Math.min(fn[i - coins[j]] + 1, min);
                }
            }
            fn[i] = min != Integer.MAX_VALUE ? min : -1;
        }
        return fn[amount];
    }
}
